import numpy as np
import math
import matplotlib.pyplot as plt
import random

path = "./resources/data.txt"
data = []


def loadData(path):
    with open(path, 'r') as fp:
        for line in fp.readlines():
            tempList = line.strip().split(',')
            data.append([float(tempList[1]), float(tempList[2])])
    fp.close()


def showData(clustering):
    color = []
    size = [25, 100]
    plt.title('AGNES')
    plt.xlabel('density')
    plt.ylabel('sweetness')
    for i in range(len(clustering)):
        color.extend(["#" + ''.join([random.choice('0123456789ABCDEF') for j in range(6)])])
    for i in range(len(clustering)):
        for j in range(len(clustering[i])):
            if 8 <= clustering[i][j] <= 20:
                index = 0
            else:
                index = 1
            plt.scatter(data[clustering[i][j]][0], data[clustering[i][j]][1], c=color[i], s=size[index])
    plt.show()


def distance(ci, cj):
    data_array = np.array(data)
    maxDistance = -1
    for i in range(len(ci)):
        for j in range(len(cj)):
            dist = np.linalg.norm(data_array[ci[i]]-data_array[cj[j]])
            if dist > maxDistance:
                maxDistance = dist
    return maxDistance


# 找距离最近的两个聚类簇,返回最小距离，以及点下标
def find_min(distanceArray):

    length = len(distanceArray)
    minDistance = float('INF')
    (pi, pj) = (-1, -1)
    for i in range(length):
        for j in range(i+1, length):
            if distanceArray[i][j] < minDistance and distanceArray[i][j] != 0:
                minDistance = distanceArray[i][j]
                (pi, pj) = (i, j)
    return pi, pj


def AGNES(k):
    c = {}
    sampleNumber = len(data)
    distanceArray = [[0 for i in range(sampleNumber)] for j in range(sampleNumber)]
    # 初始化单样本簇类
    for i in range(sampleNumber):
        c[i] = []
        c[i].append(i)
    # 初始化聚类簇距离矩阵
    for i in range(sampleNumber):
        for j in range(sampleNumber):
            distanceArray[i][j] = distance(c[i], c[j])
            distanceArray[j][i] = distanceArray[i][j]
    # 设置当前聚类簇个数
    q = sampleNumber
    # 找出当前聚类簇个数
    while q > k:
        pi, pj = find_min(distanceArray)
        # 更新聚类簇,重新编号
        c[pi].extend(c[pj])
        for i in range(pj+1, q):
            c[i-1] = c[i]
        del c[q-1]
        # 更新距离矩阵,删除pj行和列
        distanceArray = np.delete(distanceArray, pj, axis=0)
        distanceArray = np.delete(distanceArray, pj, axis=1)
        # 重新计算距离矩阵
        q = q-1
        for j in range(q):
            distanceArray[pi][j] = distance(c[pi], c[j])
            distanceArray[j][pi] = distanceArray[pi][j]
    return c


if __name__ == '__main__':
    loadData(path)
    c = AGNES(4)
    print(c)
    showData(c)